﻿#ifndef __SS_TRIE_TREE_H__
#define __SS_TRIE_TREE_H__
#include "ssTrieNode.h"
#include "ssTrieTreeDef.h"

namespace StarSeeker
{

	template<typename T_KEY, typename T_VALUE>
	class ssTrieTree
	{
	public:
		ssTrieTree();
		~ssTrieTree();
		ssTrieTree(const ssTrieTree& dic);
		void operator= (const ssTrieTree& dic);

		//查找
		ssTrieNode<T_KEY, T_VALUE>* Find(const T_KEY* arr, ulint len);
		//插入
		ssPair<ssTrieNode<T_KEY, T_VALUE>*, error_t> Insert(ssTrieNode<T_KEY, T_VALUE>* parent, T_KEY k, T_VALUE* val);
		ssPair<ssTrieNode<T_KEY, T_VALUE>*, error_t> Insert(const T_KEY* arr, ulint len, T_VALUE* val);
		//删除
		error_t Remove(ssTrieNode<T_KEY, T_VALUE>* node);
		error_t Remove(const T_KEY* arr, ulint len);
		//返回节点数
		ulint GetCount() { return m_count; }
		//清空树
		void Empty();
	private:
		//复制对象
		void CopyFrom(const ssTrieTree& dic);
		//遍历删除节点
		void RecursionEmpty(ssTrieNode<T_KEY, T_VALUE>* itr);
		//遍历复制
		void RecursionCopy(const ssTrieNode<T_KEY, T_VALUE>* itr, ssTrieNode<T_KEY, T_VALUE>* parent);
	private:
		ssTrieNode<T_KEY, T_VALUE>			m_root;
		ulint								m_count;
	};

	template<typename T_KEY, typename T_VALUE>
	inline ssTrieTree<T_KEY, T_VALUE>::ssTrieTree()
	{
		m_root.m_pOnwer = this;
		m_count = 0;
	}

	template<typename T_KEY, typename T_VALUE>
	inline ssTrieTree<T_KEY, T_VALUE>::~ssTrieTree()
	{
		Empty();
	}

	template<typename T_KEY, typename T_VALUE>
	inline ssTrieTree<T_KEY, T_VALUE>::ssTrieTree(const ssTrieTree & dic)
	{
		m_root.m_pOnwer = this;
		m_count = 0;
		CopyFrom(dic);
	}

	template<typename T_KEY, typename T_VALUE>
	void ssTrieTree<T_KEY, T_VALUE>::operator=(const ssTrieTree& dic)
	{
		Empty();
		CopyFrom(dic);
	}

	template<typename T_KEY, typename T_VALUE>
	inline ssTrieNode<T_KEY, T_VALUE> * ssTrieTree<T_KEY, T_VALUE>::Find(const T_KEY* arr, ulint len)
	{
		ssTrieNode<T_KEY, T_VALUE>* node = &m_root;
		for (ulint i = 0; i < len; i++)
		{
			typename ssMap<T_KEY, ssTrieNode<T_KEY, T_VALUE>*>::Iterator itr = node->m_children.Find(arr[i]);
			if (!itr.IsVaild())
			{
				return 0;
			}
			node = itr.Second();
		}
		return node;
	}

	template<typename T_KEY, typename T_VALUE>
	inline ssPair<ssTrieNode<T_KEY, T_VALUE>*, error_t> ssTrieTree<T_KEY, T_VALUE>::Insert(ssTrieNode<T_KEY, T_VALUE>* parent, T_KEY k, T_VALUE * val)
	{
		if (parent && parent->m_pOnwer==this)
		{
			typename ssMap<T_KEY, ssTrieNode<T_KEY, T_VALUE>*>::Iterator itr = parent->m_children.Find(k);
			if (itr.IsVaild())
			{
				return ssPair<ssTrieNode<T_KEY, T_VALUE>*, error_t>(itr.Second(), SS_DICT_KEY_EXISTED);
			}
			ssTrieNode<T_KEY, T_VALUE>* newNode = new ssTrieNode<T_KEY, T_VALUE>;
			newNode->m_pParent = parent;
			newNode->m_pOnwer = this;
			newNode->m_key = k;
			newNode->m_pValue = val;
			ssPair<typename ssMap<T_KEY, stdTrieNode<T_KEY, T_VALUE>*>::Iterator, error_t> ret = parent->m_children.Insert(k, newNode);
			if (ret.second==0)
			{
				++m_count;
				return ssPair<ssTrieNode<T_KEY, T_VALUE>*, error_t>(ret->first.Second(), SS_DICT_OK);
			}
			else
			{
				delete newNode;
				return ssPair<ssTrieNode<T_KEY, T_VALUE>*, error_t>(0, SS_DICT_CREATE_NODE_FAILED);
			}
		}
		return ssPair<ssTrieNode<T_KEY, T_VALUE>*, error_t>(0, SS_DICT_CREATE_NODE_FAILED);
	}

	template<typename T_KEY, typename T_VALUE>
	inline ssPair<ssTrieNode<T_KEY, T_VALUE>*, error_t> ssTrieTree<T_KEY, T_VALUE>::Insert(const T_KEY* arr, ulint len, T_VALUE* val)
	{
		if (arr == 0 || len == 0)
		{
			return ssPair<ssTrieNode<T_KEY, T_VALUE>*, error_t>(0, SS_DICT_KEY_ILLEGAL);
		}
		ssTrieNode<T_KEY, T_VALUE>* node = &m_root;
		for (ulint i = 0; i < len; i++)
		{
			typename ssMap<T_KEY, ssTrieNode<T_KEY, T_VALUE>*>::Iterator itr = node->m_children.Find(arr[i]);
			if (!itr.IsVaild())
			{
				ssTrieNode<T_KEY, T_VALUE>* newNode = new ssTrieNode<T_KEY, T_VALUE>;
				newNode->m_pParent = node;
				newNode->m_pOnwer = this;
				newNode->m_key = arr[i];
				if (i == len - 1)
					newNode->m_pValue = val;
				ssPair<typename ssMap<T_KEY, ssTrieNode<T_KEY, T_VALUE>*>::Iterator, error_t> ret = node->m_children.Insert(arr[i], newNode);
				if (ret.second==0)
				{
					node = ret.first.Second();
				}
				else
				{
					delete newNode;
					return ssPair<ssTrieNode<T_KEY, T_VALUE>*, error_t>(0, SS_DICT_CREATE_NODE_FAILED);
				}
			}
			else
			{
				node = itr.Second();
				if (i == len - 1)
					return ssPair<ssTrieNode<T_KEY, T_VALUE>*, error_t>(node, SS_DICT_KEY_EXISTED);
			}
		}
		++m_count;
		return ssPair<ssTrieNode<T_KEY, T_VALUE>*, error_t>(node, SS_DICT_OK);
	}

	template<typename T_KEY, typename T_VALUE>
	error_t StarSeeker::ssTrieTree<T_KEY, T_VALUE>::Remove(ssTrieNode<T_KEY, T_VALUE>* node)
	{
		if (node == 0)
		{
			return SS_DICT_KEY_NOTEXISTED;
		}
		if (node->m_pOnwer != this)
		{
			return SS_DICT_DEL_ILLEGAL;
		}
		if (node->m_pParent == 0)
		{
			return SS_DICT_DEL_ILLEGAL;
		}
		if (node->m_children.Size()==0)//叶节点
		{
			ssTrieNode<T_KEY, T_VALUE>* parent = node->m_pParent;
			while (node && parent)
			{
				if (node->m_pValue)
				{
					delete node->m_pValue;
					node->m_pValue = 0;
					node->m_pOnwer = 0;
				}
				parent->m_children.Erase(node->m_key);
				delete node;
				node = parent;
				if (node)
				{
					parent = node->m_pParent;
				}
				if (node->m_children.Size() || node->m_pValue)
				{
					break;
				}
			}
		}
		else
		{
			if (node->m_pValue)
			{
				delete node->m_pValue;
				node->m_pValue = 0;
			}
		}
		--m_count;
		return SS_DICT_OK;
	}

	template<typename T_KEY, typename T_VALUE>
	inline error_t ssTrieTree<T_KEY, T_VALUE>::Remove(const T_KEY* arr, ulint len)
	{
		ssTrieNode<T_KEY, T_VALUE>* node = Find(arr, len);
		return Remove(node);
	}

	template<typename T_KEY, typename T_VALUE>
	inline void ssTrieTree<T_KEY, T_VALUE>::Empty()
	{
		m_count = 0;
		RecursionEmpty(&m_root);
	}

	template<typename T_KEY, typename T_VALUE>
	inline void ssTrieTree<T_KEY, T_VALUE>::CopyFrom(const ssTrieTree & dic)
	{
		RecursionCopy(&dic.m_root, &m_root);
	}

	template<typename T_KEY, typename T_VALUE>
	inline void ssTrieTree<T_KEY, T_VALUE>::RecursionEmpty(ssTrieNode<T_KEY, T_VALUE>* itr)
	{
		if (itr)
		{
			if (itr->m_children.Size())
			{
				for (typename ssMap<T_KEY, ssTrieNode<T_KEY, T_VALUE>*>::Iterator i = itr->m_children.Begin(); i != itr->m_children.End(); ++i)
				{
					RecursionEmpty(i.Second());
				}
				itr->m_children.Empty();
			}
			if (itr->m_pValue)
			{
				delete itr->m_pValue;
				itr->m_pValue = 0;
			}
			if (itr->m_pParent)
			{
				itr->m_pOnwer = 0;
				delete itr;
			}
		}
	}

	template<typename T_KEY, typename T_VALUE>
	inline void ssTrieTree<T_KEY, T_VALUE>::RecursionCopy(const ssTrieNode<T_KEY, T_VALUE>* itr, ssTrieNode<T_KEY, T_VALUE>* parent)
	{
		if (itr)
		{
			T_VALUE* pValue = 0;
			if (itr->m_pValue)
			{
				pValue = new T_VALUE;
				*pValue = *itr->m_pValue;
			}
			Insert(parent, itr->m_key, pValue);
			if (itr->m_children.Size())
			{
				for (typename ssMap<T_KEY, ssTrieNode<T_KEY, T_VALUE>*>::Iterator i = itr->m_children.Begin(); i != itr->m_children.End(); ++i)
				{
					RecursionCopy(i->second, itr);
				}
			}
		}
	}
}
#endif
